﻿class Solution
{
	bool vis[7][7];
	int m, n;
public:
	bool exist(vector<vector<char>>& board, string word)
	{
		m = board.size(), n = board[0].size();
		for (int i = 0; i < m; i++)
			for (int j = 0; j < n; j++)
			{
				if (board[i][j] == word[0])
				{
					vis[i][j] = true;
					if (dfs(board, i, j, word, 1)) return true;
					vis[i][j] = false;
				}
			}
		return false;
	}
	int dx[4] = { 0, 0, -1, 1 };
	int dy[4] = { 1, -1, 0, 0 };
	bool dfs(vector<vector<char>>& board, int i, int j, string& word, int pos)
	{
		if (pos == word.size()) return true;
		// 向量的⽅式，定义上下左右四个位置 
		for (int k = 0; k < 4; k++)
		{
			int x = i + dx[k], y = j + dy[k];
			if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y]
				== word[pos])
			{
				vis[x][y] = true;
				if (dfs(board, x, y, word, pos + 1)) return true;
				vis[x][y] = false;
			}
		}
		return false;
	}
};